package dnaSequencer;

import java.util.ArrayList;

public class AlgorytmyGrafowe {

    // Zmienne niezbedne do poszukiwania silnie spojnych skladowych
    private static boolean[] odwiedzone;
    private static int[] postOrder;
    private static int[] przynaleznosc;
    private static ArrayList<Integer>[] listaNastepnikow;
    private static ArrayList<Integer>[] listaPoprzednikow;
    private static int size;
    private static int time;
    private static int skladowa;
    private static int maxTime;
    private static int[] depth;
    private static ArrayList<Integer> odwiedzoneSkladowe; 

    public static ArrayList<Integer>[] utworzListeNastepnikow(
            ArrayList<String> oligonukleotydy) {
        ArrayList<Integer>[] nastepniki = new ArrayList[oligonukleotydy.size()];
        int len = oligonukleotydy.get(0).length();

        for (String pocz : oligonukleotydy) {
            for (String kon : oligonukleotydy) {
                if (pocz == kon) {
                    continue;
                } else if (pocz.endsWith(kon.substring(0, len - 1))) {
                    int poczIdx = oligonukleotydy.indexOf(pocz);

                    if (nastepniki[poczIdx] == null) {
                        nastepniki[poczIdx] = new ArrayList<Integer>();
                    }
                    nastepniki[poczIdx].add(oligonukleotydy.indexOf(kon));
                }
            }
        }

        return nastepniki;
    }

    public static ArrayList<Integer>[] utworzListePoprzednikow(
            ArrayList<String> oligonukleotydy) {
        ArrayList<Integer>[] poprzedniki = new ArrayList[oligonukleotydy.size()];
        int len = oligonukleotydy.get(0).length();

        for (String kon : oligonukleotydy) {
            for (String pocz : oligonukleotydy) {
                if (pocz == kon) {
                    continue;
                } else if (pocz.endsWith(kon.substring(0, len - 1))) {
                    int konIdx = oligonukleotydy.indexOf(kon);

                    if (poprzedniki[konIdx] == null) {
                        poprzedniki[konIdx] = new ArrayList<Integer>();
                    }
                    poprzedniki[konIdx].add(oligonukleotydy.indexOf(pocz));
                }
            }
        }

        return poprzedniki;
    }

    public static int[] znajdzSilnieSpojneSkladowe(
            ArrayList<Integer>[] _listaPoprzednikow,
            ArrayList<Integer>[] _listaNastepnikow) {
        listaNastepnikow = _listaNastepnikow;
        listaPoprzednikow = _listaPoprzednikow;
        size = listaNastepnikow.length;
        time = 1;
        skladowa = 1;

        odwiedzone = new boolean[size];
        postOrder = new int[size];
        przynaleznosc = new int[size];

        for (int i = 0; i < size; i++) {
            odwiedzone[i] = false;
        }

        for (int i = 0; i < size; i++) {
            if (!odwiedzone[i]) {
                Visit1(i);
            }
        }

        for (int i = 0; i < size; i++) {
            odwiedzone[i] = false;
        }

        for (int i = 0; i < size; i++) {
            if (!odwiedzone[postOrder[i]]) {
                Visit2(postOrder[i]);
                skladowa++;
            }
        }

        return przynaleznosc;
    }

    private static void Visit1(int v) {
        odwiedzone[v] = true;

        if (listaNastepnikow[v] != null) {
            for (Integer i : listaNastepnikow[v]) {
                if (!odwiedzone[i]) {
                    Visit1(i);
                }
            }
        }

        postOrder[size - time] = v;
        time++;
    }

    private static void Visit2(int v) {
        przynaleznosc[v] = skladowa;
        odwiedzone[v] = true;

        if (listaPoprzednikow[v] != null) {
            for (Integer i : listaPoprzednikow[v]) {
                if (!odwiedzone[i]) {
                    Visit2(i);
                }
            }
        }
    }

    // dopoki zwraca true, sa jakies niepojedyncze skladowe
    public static boolean usunCykle(ArrayList<Integer>[] listaPoprz,
            ArrayList<Integer>[] listaNast, int[] skladowe) {
        int liczbaSkladowych = 0;

        // ile skladowych?
        for (int i = 0; i < skladowe.length; i++) {
            if (skladowe[i] > liczbaSkladowych) {
                liczbaSkladowych = skladowe[i];
            }
        }

        if (liczbaSkladowych == skladowe.length) {
            return false;
        }

        // dla kazdej skladowej...
        for (int i = 1; i <= liczbaSkladowych; i++) {
            // sprawdzamy czy skladowa ma wiecej niz 1 wierzcholek
            int tmp = 0;
            for (int j = 0; j < skladowe.length; j++) {
                if (skladowe[j] == i) {
                    tmp++;
                }
                if (tmp > 2) {
                    break;
                }
            }
            
            
            ArrayList<Integer> wierzcholkiSkladowej;
            Integer wierzcholekZMaksem = null;
            int maxDfs = 0;
            int temp;
            
            if (tmp == 1) {
                continue;
            } else {
                wierzcholkiSkladowej = new ArrayList<Integer>();
                for (Integer j = 0; j < skladowe.length; j++) {
                    if (skladowe[j] == i) {
                        wierzcholkiSkladowej.add(j);
                    }
                }
                for (Integer wierzcholek : wierzcholkiSkladowej) {
					/*if (skladowe[wierzcholek] == i) {
						continue;
					}*/
                	temp = dfsDuringSSS(wierzcholek);
                    if (temp > maxDfs) {
                        wierzcholekZMaksem = wierzcholek;
                        maxDfs = temp;
                    }
                }
                
                if (wierzcholekZMaksem == null)
                    wierzcholekZMaksem = wierzcholkiSkladowej.get(0);
                
                for (int l = 0; l < listaNast[wierzcholekZMaksem].size(); l++) {
                    if (skladowe[listaNast[wierzcholekZMaksem].get(l)] == i) {
                        listaPoprz[listaNast[wierzcholekZMaksem].get(l)]
                                .remove(wierzcholekZMaksem);
                        listaNast[wierzcholekZMaksem].remove(l);
                    }
                }
                
                return true;
                
                /*
                 * dla wszystkich elementow nalezacych do danej skladowej
                 * sprawdzamy, czy sa polaczone z poprzednia skladowa, jesli tak
                 * to usuwamy luk laczacy ten element z poprzednikiem z danej
                 * skladowej usuwajac cykl
                 * 
                 * a w sumie to, jesli numer skladowej < od liczby skladowych/2
                 * to usuwamy poprzednika pierwszego elementu cyklu, w
                 * przeciwnym wypadku nastepnika ostatniego elementu cyklu
                 */
                /*if (liczbaSkladowych == 1) {
                    for (Integer j = 0; j < skladowe.length; j++) {
                        if (skladowe[j] == i) {
                            for (int l = 0; l < listaNast[j].size(); l++) {
                                if (skladowe[listaNast[j].get(l)] == i) {
                                    listaPoprz[listaNast[j].get(l)].remove(j);
                                    listaNast[j].remove(l);
                                }
                            }
                            break;
                        }
                    }
                } else {
                    for (Integer j = 0; j < skladowe.length; j++) {
                        if (skladowe[j] == i) {
                            if (i < liczbaSkladowych / 2) {
                                for (int k = 0; k < listaNast[j].size(); k++) {
                                    if (skladowe[listaNast[j].get(k)] > i) {
                                        for (int l = 0; l < listaNast[j].size(); l++) {
                                            if (skladowe[listaNast[j].get(l)] == i) {
                                                listaPoprz[listaNast[j].get(l)]
                                                        .remove(j);
                                                listaNast[j].remove(l);
                                            }
                                        }
                                    }
                                }
                            } else {
                                for (int k = 0; k < listaPoprz[j].size(); k++) {
                                    if (skladowe[listaPoprz[j].get(k)] < i) {
                                        for (int l = 0; l < listaPoprz[j]
                                                .size(); l++) {
                                            if (skladowe[listaPoprz[j].get(l)] == i) {
                                                listaNast[listaPoprz[j].get(l)]
                                                        .remove(j);
                                                listaPoprz[j].remove(l);
                                            }
                                        }
                                    }
                                }
                            }  
                        }
                    }
                } */           
            }
        }

        return true;
    }

    public static int[] topSort(ArrayList<Integer>[] listaPoprz,
            ArrayList<Integer>[] listaNast) {
        ArrayList<Integer>[] lNastepnikow = new ArrayList[listaNast.length];
        ArrayList<Integer>[] lPoprzednikow = new ArrayList[listaPoprz.length];

        for (int i = 0; i < listaNast.length; i++) {
            if (listaNast[i] == null)
                lNastepnikow[i] = null;

            else {
                lNastepnikow[i] = new ArrayList<Integer>();
                for (int a : listaNast[i])
                    lNastepnikow[i].add(a);

            }
        }

        for (int i = 0; i < listaPoprz.length; i++) {
            if (listaPoprz[i] == null)
                lPoprzednikow[i] = null;
            else {
                lPoprzednikow[i] = new ArrayList<Integer>();
                for (int a : listaPoprz[i])
                    lPoprzednikow[i].add(a);
            }
        }

        ArrayList<Integer> kolejka = new ArrayList<Integer>();
        ArrayList<Integer> wynik = new ArrayList<Integer>();

        for (int i = 0; i < lPoprzednikow.length; i++) {
            // System.out.println("Wierzchołek " + i + " ma " +
            // lPoprzednikow[i].size() + " poprzednikow ");
            if (lPoprzednikow[i] == null || lPoprzednikow[i].size() == 0) {
                kolejka.add(i);
            }
        }

        while (kolejka.size() > 0) {
            int n = kolejka.get(0);
            wynik.add(n);
            kolejka.remove(0);
            /*
             * System.out.println("Wierzchołek " + n); if (lNastepnikow[n] !=
             * null) System.out.println("Ma jeszcze " + lNastepnikow[n].size() +
             * " nastepnikow"); else continue;
             */
            if (lNastepnikow[n] == null || lNastepnikow[n].size() == 0)
                continue;

            while (lNastepnikow[n].size() > 0) {
                int nastepnik = lNastepnikow[n].get(0);
                lPoprzednikow[nastepnik].remove((Integer) n);
                lNastepnikow[n].remove((Integer) nastepnik);
                // System.out.println("Usuwam polaczenie " + n +" -> " +
                // nastepnik);
                if (lPoprzednikow[nastepnik].size() == 0) {
                    lPoprzednikow[nastepnik] = null;
                    kolejka.add(nastepnik);
                    // System.out.println("Dodaje do kolejki wierzcholek " +
                    // nastepnik);
                }
            }

        }

        int[] tablicaWynikowa = new int[lNastepnikow.length];
        for (int i = 0; i < wynik.size(); i++)
            tablicaWynikowa[wynik.get(i)] = i + 1;

        return tablicaWynikowa;

    }

    public static int[] wierzcholkiBezPoprz(ArrayList<Integer>[] listaPoprz) {

        ArrayList<Integer> kolejka = new ArrayList<Integer>();
        for (int i = 0; i < listaPoprz.length; i++) {
            if (listaPoprz[i] == null || listaPoprz[i].size() == 0) {
                kolejka.add(i);
            }
        }

        int[] tablicaWynikowa = new int[kolejka.size()];
        for (int i = 0; i < kolejka.size(); i++)
            tablicaWynikowa[i] = kolejka.get(i);

        return tablicaWynikowa;
    }

    public static int[] dfs(ArrayList<Integer>[] listaNast, int[] sss) {
        listaNastepnikow = listaNast;

        time = 1;
        odwiedzone = new boolean[size];
        depth = new int[size];

        for (int i = 0; i < size; i++) {
            odwiedzone[i] = false;
        }

        for (int i = 1; i < size + 1; i++) {
            for (int j = 0; j < size; j++) {
                if (sss[j] == i && !odwiedzone[j]) {
                    Visit3(j, time);
                }
            }
        }
        return depth;
    }

    public static int[] dfsSpecial(ArrayList<Integer>[] listaNast, int[] wbp, int totalWordsCount) {
        odwiedzone = new boolean[size];
        depth = new int[size];
        int[] maxDepth = new int[size];

        int mDepth = 0;
        
        // zaczynajac od wszystkich wierzcholkow nieodwiedzonych
        for (int i = 0; i < wbp.length; i++) {
            time = 1;
            maxTime = 0;
            for (int j = 0; j < size; j++) {
                odwiedzone[j] = false;
                depth[j] = 0;
            }
            
            for (int j = i; j < wbp.length + i; j++) {
            	 if (!odwiedzone[wbp[j % wbp.length]]) {
                    Visit3(wbp[j % wbp.length], time);
                }
            }
            
            //jesli po wykonaniu iteracji, zmienia sie max, zapamietujemy nowego maxa i wartosci tablic
            if (mDepth < maxTime) {
                for (int j = 0; j < maxDepth.length; j++) {
                    maxDepth[j] = depth[j];
                }
                mDepth = maxTime;
                
                if (maxTime > totalWordsCount)
                	return maxDepth;
            }
            
        }

        return maxDepth;
    }
    
	public static int dfsDuringSSS(int start) {
		odwiedzoneSkladowe = new ArrayList<Integer>();
		
		odwiedzone = new boolean[size];
		depth = new int[size];

		maxTime = 0;

		time = 1;
		for (int j = 0; j < size; j++) {
			odwiedzone[j] = false;
			depth[j] = 0;
		}

		Visit4(start, time);

		return maxTime;
	}

    private static void Visit3(int v, int t) {
        odwiedzone[v] = true;
        depth[v] = t;
        t++;
        if (t > maxTime)
            maxTime = t;
        if (listaNastepnikow[v] != null) {
            for (Integer i : listaNastepnikow[v]) {
                if (!odwiedzone[i]) {
                    Visit3(i, t);
                } else {
                	if (t > depth[i])
                		Visit3(i, t);
                }
            }
        }
    }
    
    private static void Visit4(int v, int t) {
        int sklad = przynaleznosc[v];
        
        if (!odwiedzoneSkladowe.contains(sklad))
        	odwiedzoneSkladowe.add(sklad);
    	
    	odwiedzone[v] = true;
        depth[v] = t;
        t++;
        if (t > maxTime)
            maxTime = t;
        if (listaNastepnikow[v] != null) {
            for (Integer i : listaNastepnikow[v]) {
                if (!odwiedzone[i]) {
                    Visit4(i, t);
                } 
            }
        }
    }

}
